package com.simon.study.algorithm.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <p>
 *
 * @author simon
 */
public class MaxProfit01648 {

    public static void main(String[] args) {
        int[] inventory = new int[]{1000000000};
        int orders = 1000000000;

        maxProfit(inventory, orders);
    }

    static class Pair{
        Integer num;
        int times;

        public Pair(){}
        public Pair(Integer num, int times){
            this.num   = num;
            this.times = times;
        }
    }


    public static int maxProfit(int[] inventory, int orders) {
        Map<Integer, Pair> mappings = new HashMap<>();

        for(int i=0; i < inventory.length; i++){
            Pair np = mappings.get(inventory[i]);
            if( np == null ){
                np = new Pair(inventory[i], 0);
                mappings.put(inventory[i], np);
            }
            np.times++;
        }

        List<Integer> nums = new ArrayList<>();
        nums.addAll(mappings.keySet());

        Collections.sort(nums);

        Deque<Pair> stack = new ArrayDeque<>();
        for(int i=0; i<nums.size(); i++){
            stack.push( mappings.get(nums.get(i)) );
        }

        long sum = 0;
        while( orders !=0 && !stack.isEmpty() ){
            Pair p = stack.pop();

            if(p.num == 0){ continue; }

            Integer nn = p.num - 1;
            Pair np    = mappings.get(nn);

            if(orders >= p.times){
                orders = orders - p.times;

                mappings.remove(p.num);
                if( np == null ){
                    np = new Pair(nn, p.times);
                    mappings.put(nn, np);
                    stack.push(np);
                }else{
                    np.times = np.times + p.times;
                }
                sum = sum + (long)p.times * p.num;
            }else{
                long k = orders;
                orders = 0;
                sum = sum + k * p.num;
            }
        }

        return (int)(sum%100000007L);
    }
}
